package com.lw.leetcode.tree.c;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1483. 树节点的第 K 个祖先
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/28 17:34
 */
public class TreeAncestor {


    public static void main(String[] args) {

        // [null,1,0,-1]
        int[] arr = {-1, 0, 0, 1, 1, 2, 2};
        int n = 7;
        TreeAncestor test = new TreeAncestor(n, arr);
        System.out.println(test.getKthAncestor(3, 1));
        System.out.println(test.getKthAncestor(5, 2));
        System.out.println(test.getKthAncestor(6, 3));

    }


    private int[] parent;
    private Map<Integer, Node> map = new HashMap<>();

    public TreeAncestor(int n, int[] parent) {
        this.parent = parent;
        Node root = new Node(0);
        map.put(0, root);
        for (int i = 1; i < n; i++) {
            find(i);
        }
    }

    public int getKthAncestor(int node, int k) {
        Node no = map.get(node);
        for (int i = 15; i >= 0; i--) {
            if (((k >> i) & 1) == 1) {
                no = no.arr[i];
                if (no == null) {
                    return -1;
                }
            }
        }
        return no.val;
    }

    private void find(int index) {
        if (map.get(index) != null) {
            return;
        }
        Node item = new Node(index);
        map.put(index, item);
        Node[] arr = item.arr;

        int p = parent[index];
        Node node = map.get(p);
        if (node == null) {
            find(p);
        }
        Node pn = map.get(p);
        arr[0] = pn;

        for (int i = 1; i < arr.length; i++) {
            Node last = arr[i - 1];
            if (last != null && last.arr[i - 1] != null) {
                arr[i] = last.arr[i - 1];
            } else {
                break;
            }
        }

    }

    private static class Node {
        private int val;
        private Node[] arr = new Node[16];

        public Node(int val) {
            this.val = val;
        }
    }
}
